package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC34 {

    public int[] searchRange(int[] nums, int target) {
        return searchRangeRecur(nums, 0, nums.length - 1, target);
    }

    public int[] searchRangeRecur(int[] arr, int lb, int ub, int target) {
        int[] range = {-1, -1};
        if (null == arr || arr.length <= 0 || lb > ub) {
            return range;
        }

        if (lb == ub) {
            if (arr[lb] == target) {
                range[0] = lb;
                range[1] = lb;
                return range;
            } else {
                return range;
            }
        }

        int mid = (ub + lb) / 2;
        if (arr[mid] == target) {
            int[] leftRange = searchRangeRecur(arr, lb, mid - 1, target);
            int[] rightRange = searchRangeRecur(arr, mid + 1, ub, target);
            range[0] = leftRange[0] > -1 ? leftRange[0] : mid;
            range[1] = rightRange[1] > -1 ? rightRange[1] : mid;
            return range;
        }

        if (arr[mid] > target) {
            return searchRangeRecur(arr, lb, mid - 1, target);
        }

        return searchRangeRecur(arr, mid + 1, ub, target);
    }


    public static void main(String[] args) {
        LC34 an = new LC34();
        int arr[] = {5, 7, 7, 8, 8, 10};
        System.out.println(an.searchRange(arr, 8));
    }
}
